
lst = [10, 90, 28, 89, 66, 58, 77, 32]

# 归并排序
def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    else:
        mid = len(lst)//2
        left = merge_sort(lst[:mid])
        right = merge_sort(lst[mid:])
        return merge(left, right)


def merge(lst1, lst2):
    lst = []

    while lst1 and lst2:
        if lst1[0] <lst2[0]:
            lst.append(lst1.pop(0))
        else:
            lst.append(lst2.pop(0))
    lst.extend(lst1+lst2)
    return lst


print(merge_sort(lst))
